home *** CD-ROM | disk | FTP | other *** search
/ Chip 2007 January, February, March & April / Chip-Cover-CD-2007-02.iso / Pakiet bezpieczenstwa / mini Pentoo LiveCD 2006.1 / mpentoo-2006.1.iso / livecd.squashfs / usr / lib / python2.4 / test / test_generators.pyo (.txt) < prev    next >
Python Compiled Bytecode  |  2005-10-18  |  34KB  |  363 lines
  1. # Source Generated with Decompyle++
  2. # File: in.pyo (Python 2.4)
  3.  
  4. tutorial_tests = '\nLet\'s try a simple generator:\n\n    >>> def f():\n    ...    yield 1\n    ...    yield 2\n\n    >>> for i in f():\n    ...     print i\n    1\n    2\n    >>> g = f()\n    >>> g.next()\n    1\n    >>> g.next()\n    2\n\n"Falling off the end" stops the generator:\n\n    >>> g.next()\n    Traceback (most recent call last):\n      File "<stdin>", line 1, in ?\n      File "<stdin>", line 2, in g\n    StopIteration\n\n"return" also stops the generator:\n\n    >>> def f():\n    ...     yield 1\n    ...     return\n    ...     yield 2 # never reached\n    ...\n    >>> g = f()\n    >>> g.next()\n    1\n    >>> g.next()\n    Traceback (most recent call last):\n      File "<stdin>", line 1, in ?\n      File "<stdin>", line 3, in f\n    StopIteration\n    >>> g.next() # once stopped, can\'t be resumed\n    Traceback (most recent call last):\n      File "<stdin>", line 1, in ?\n    StopIteration\n\n"raise StopIteration" stops the generator too:\n\n    >>> def f():\n    ...     yield 1\n    ...     raise StopIteration\n    ...     yield 2 # never reached\n    ...\n    >>> g = f()\n    >>> g.next()\n    1\n    >>> g.next()\n    Traceback (most recent call last):\n      File "<stdin>", line 1, in ?\n    StopIteration\n    >>> g.next()\n    Traceback (most recent call last):\n      File "<stdin>", line 1, in ?\n    StopIteration\n\nHowever, they are not exactly equivalent:\n\n    >>> def g1():\n    ...     try:\n    ...         return\n    ...     except:\n    ...         yield 1\n    ...\n    >>> list(g1())\n    []\n\n    >>> def g2():\n    ...     try:\n    ...         raise StopIteration\n    ...     except:\n    ...         yield 42\n    >>> print list(g2())\n    [42]\n\nThis may be surprising at first:\n\n    >>> def g3():\n    ...     try:\n    ...         return\n    ...     finally:\n    ...         yield 1\n    ...\n    >>> list(g3())\n    [1]\n\nLet\'s create an alternate range() function implemented as a generator:\n\n    >>> def yrange(n):\n    ...     for i in range(n):\n    ...         yield i\n    ...\n    >>> list(yrange(5))\n    [0, 1, 2, 3, 4]\n\nGenerators always return to the most recent caller:\n\n    >>> def creator():\n    ...     r = yrange(5)\n    ...     print "creator", r.next()\n    ...     return r\n    ...\n    >>> def caller():\n    ...     r = creator()\n    ...     for i in r:\n    ...             print "caller", i\n    ...\n    >>> caller()\n    creator 0\n    caller 1\n    caller 2\n    caller 3\n    caller 4\n\nGenerators can call other generators:\n\n    >>> def zrange(n):\n    ...     for i in yrange(n):\n    ...         yield i\n    ...\n    >>> list(zrange(5))\n    [0, 1, 2, 3, 4]\n\n'
  5. pep_tests = '\n\nSpecification:  Yield\n\n    Restriction:  A generator cannot be resumed while it is actively\n    running:\n\n    >>> def g():\n    ...     i = me.next()\n    ...     yield i\n    >>> me = g()\n    >>> me.next()\n    Traceback (most recent call last):\n     ...\n      File "<string>", line 2, in g\n    ValueError: generator already executing\n\nSpecification: Return\n\n    Note that return isn\'t always equivalent to raising StopIteration:  the\n    difference lies in how enclosing try/except constructs are treated.\n    For example,\n\n        >>> def f1():\n        ...     try:\n        ...         return\n        ...     except:\n        ...        yield 1\n        >>> print list(f1())\n        []\n\n    because, as in any function, return simply exits, but\n\n        >>> def f2():\n        ...     try:\n        ...         raise StopIteration\n        ...     except:\n        ...         yield 42\n        >>> print list(f2())\n        [42]\n\n    because StopIteration is captured by a bare "except", as is any\n    exception.\n\nSpecification: Generators and Exception Propagation\n\n    >>> def f():\n    ...     return 1//0\n    >>> def g():\n    ...     yield f()  # the zero division exception propagates\n    ...     yield 42   # and we\'ll never get here\n    >>> k = g()\n    >>> k.next()\n    Traceback (most recent call last):\n      File "<stdin>", line 1, in ?\n      File "<stdin>", line 2, in g\n      File "<stdin>", line 2, in f\n    ZeroDivisionError: integer division or modulo by zero\n    >>> k.next()  # and the generator cannot be resumed\n    Traceback (most recent call last):\n      File "<stdin>", line 1, in ?\n    StopIteration\n    >>>\n\nSpecification: Try/Except/Finally\n\n    >>> def f():\n    ...     try:\n    ...         yield 1\n    ...         try:\n    ...             yield 2\n    ...             1//0\n    ...             yield 3  # never get here\n    ...         except ZeroDivisionError:\n    ...             yield 4\n    ...             yield 5\n    ...             raise\n    ...         except:\n    ...             yield 6\n    ...         yield 7     # the "raise" above stops this\n    ...     except:\n    ...         yield 8\n    ...     yield 9\n    ...     try:\n    ...         x = 12\n    ...     finally:\n    ...         yield 10\n    ...     yield 11\n    >>> print list(f())\n    [1, 2, 4, 5, 8, 9, 10, 11]\n    >>>\n\nGuido\'s binary tree example.\n\n    >>> # A binary tree class.\n    >>> class Tree:\n    ...\n    ...     def __init__(self, label, left=None, right=None):\n    ...         self.label = label\n    ...         self.left = left\n    ...         self.right = right\n    ...\n    ...     def __repr__(self, level=0, indent="    "):\n    ...         s = level*indent + repr(self.label)\n    ...         if self.left:\n    ...             s = s + "\\n" + self.left.__repr__(level+1, indent)\n    ...         if self.right:\n    ...             s = s + "\\n" + self.right.__repr__(level+1, indent)\n    ...         return s\n    ...\n    ...     def __iter__(self):\n    ...         return inorder(self)\n\n    >>> # Create a Tree from a list.\n    >>> def tree(list):\n    ...     n = len(list)\n    ...     if n == 0:\n    ...         return []\n    ...     i = n // 2\n    ...     return Tree(list[i], tree(list[:i]), tree(list[i+1:]))\n\n    >>> # Show it off: create a tree.\n    >>> t = tree("ABCDEFGHIJKLMNOPQRSTUVWXYZ")\n\n    >>> # A recursive generator that generates Tree labels in in-order.\n    >>> def inorder(t):\n    ...     if t:\n    ...         for x in inorder(t.left):\n    ...             yield x\n    ...         yield t.label\n    ...         for x in inorder(t.right):\n    ...             yield x\n\n    >>> # Show it off: create a tree.\n    >>> t = tree("ABCDEFGHIJKLMNOPQRSTUVWXYZ")\n    >>> # Print the nodes of the tree in in-order.\n    >>> for x in t:\n    ...     print x,\n    A B C D E F G H I J K L M N O P Q R S T U V W X Y Z\n\n    >>> # A non-recursive generator.\n    >>> def inorder(node):\n    ...     stack = []\n    ...     while node:\n    ...         while node.left:\n    ...             stack.append(node)\n    ...             node = node.left\n    ...         yield node.label\n    ...         while not node.right:\n    ...             try:\n    ...                 node = stack.pop()\n    ...             except IndexError:\n    ...                 return\n    ...             yield node.label\n    ...         node = node.right\n\n    >>> # Exercise the non-recursive generator.\n    >>> for x in t:\n    ...     print x,\n    A B C D E F G H I J K L M N O P Q R S T U V W X Y Z\n\n'
  6. email_tests = '\n\nThe difference between yielding None and returning it.\n\n>>> def g():\n...     for i in range(3):\n...         yield None\n...     yield None\n...     return\n>>> list(g())\n[None, None, None, None]\n\nEnsure that explicitly raising StopIteration acts like any other exception\nin try/except, not like a return.\n\n>>> def g():\n...     yield 1\n...     try:\n...         raise StopIteration\n...     except:\n...         yield 2\n...     yield 3\n>>> list(g())\n[1, 2, 3]\n\nNext one was posted to c.l.py.\n\n>>> def gcomb(x, k):\n...     "Generate all combinations of k elements from list x."\n...\n...     if k > len(x):\n...         return\n...     if k == 0:\n...         yield []\n...     else:\n...         first, rest = x[0], x[1:]\n...         # A combination does or doesn\'t contain first.\n...         # If it does, the remainder is a k-1 comb of rest.\n...         for c in gcomb(rest, k-1):\n...             c.insert(0, first)\n...             yield c\n...         # If it doesn\'t contain first, it\'s a k comb of rest.\n...         for c in gcomb(rest, k):\n...             yield c\n\n>>> seq = range(1, 5)\n>>> for k in range(len(seq) + 2):\n...     print "%d-combs of %s:" % (k, seq)\n...     for c in gcomb(seq, k):\n...         print "   ", c\n0-combs of [1, 2, 3, 4]:\n    []\n1-combs of [1, 2, 3, 4]:\n    [1]\n    [2]\n    [3]\n    [4]\n2-combs of [1, 2, 3, 4]:\n    [1, 2]\n    [1, 3]\n    [1, 4]\n    [2, 3]\n    [2, 4]\n    [3, 4]\n3-combs of [1, 2, 3, 4]:\n    [1, 2, 3]\n    [1, 2, 4]\n    [1, 3, 4]\n    [2, 3, 4]\n4-combs of [1, 2, 3, 4]:\n    [1, 2, 3, 4]\n5-combs of [1, 2, 3, 4]:\n\nFrom the Iterators list, about the types of these things.\n\n>>> def g():\n...     yield 1\n...\n>>> type(g)\n<type \'function\'>\n>>> i = g()\n>>> type(i)\n<type \'generator\'>\n>>> [s for s in dir(i) if not s.startswith(\'_\')]\n[\'gi_frame\', \'gi_running\', \'next\']\n>>> print i.next.__doc__\nx.next() -> the next value, or raise StopIteration\n>>> iter(i) is i\nTrue\n>>> import types\n>>> isinstance(i, types.GeneratorType)\nTrue\n\nAnd more, added later.\n\n>>> i.gi_running\n0\n>>> type(i.gi_frame)\n<type \'frame\'>\n>>> i.gi_running = 42\nTraceback (most recent call last):\n  ...\nTypeError: readonly attribute\n>>> def g():\n...     yield me.gi_running\n>>> me = g()\n>>> me.gi_running\n0\n>>> me.next()\n1\n>>> me.gi_running\n0\n\nA clever union-find implementation from c.l.py, due to David Eppstein.\nSent: Friday, June 29, 2001 12:16 PM\nTo: python-list@python.org\nSubject: Re: PEP 255: Simple Generators\n\n>>> class disjointSet:\n...     def __init__(self, name):\n...         self.name = name\n...         self.parent = None\n...         self.generator = self.generate()\n...\n...     def generate(self):\n...         while not self.parent:\n...             yield self\n...         for x in self.parent.generator:\n...             yield x\n...\n...     def find(self):\n...         return self.generator.next()\n...\n...     def union(self, parent):\n...         if self.parent:\n...             raise ValueError("Sorry, I\'m not a root!")\n...         self.parent = parent\n...\n...     def __str__(self):\n...         return self.name\n\n>>> names = "ABCDEFGHIJKLM"\n>>> sets = [disjointSet(name) for name in names]\n>>> roots = sets[:]\n\n>>> import random\n>>> gen = random.WichmannHill(42)\n>>> while 1:\n...     for s in sets:\n...         print "%s->%s" % (s, s.find()),\n...     print\n...     if len(roots) > 1:\n...         s1 = gen.choice(roots)\n...         roots.remove(s1)\n...         s2 = gen.choice(roots)\n...         s1.union(s2)\n...         print "merged", s1, "into", s2\n...     else:\n...         break\nA->A B->B C->C D->D E->E F->F G->G H->H I->I J->J K->K L->L M->M\nmerged D into G\nA->A B->B C->C D->G E->E F->F G->G H->H I->I J->J K->K L->L M->M\nmerged C into F\nA->A B->B C->F D->G E->E F->F G->G H->H I->I J->J K->K L->L M->M\nmerged L into A\nA->A B->B C->F D->G E->E F->F G->G H->H I->I J->J K->K L->A M->M\nmerged H into E\nA->A B->B C->F D->G E->E F->F G->G H->E I->I J->J K->K L->A M->M\nmerged B into E\nA->A B->E C->F D->G E->E F->F G->G H->E I->I J->J K->K L->A M->M\nmerged J into G\nA->A B->E C->F D->G E->E F->F G->G H->E I->I J->G K->K L->A M->M\nmerged E into G\nA->A B->G C->F D->G E->G F->F G->G H->G I->I J->G K->K L->A M->M\nmerged M into G\nA->A B->G C->F D->G E->G F->F G->G H->G I->I J->G K->K L->A M->G\nmerged I into K\nA->A B->G C->F D->G E->G F->F G->G H->G I->K J->G K->K L->A M->G\nmerged K into A\nA->A B->G C->F D->G E->G F->F G->G H->G I->A J->G K->A L->A M->G\nmerged F into A\nA->A B->G C->A D->G E->G F->A G->G H->G I->A J->G K->A L->A M->G\nmerged A into G\nA->G B->G C->G D->G E->G F->G G->G H->G I->G J->G K->G L->G M->G\n'
  7. fun_tests = '\n\nBuild up to a recursive Sieve of Eratosthenes generator.\n\n>>> def firstn(g, n):\n...     return [g.next() for i in range(n)]\n\n>>> def intsfrom(i):\n...     while 1:\n...         yield i\n...         i += 1\n\n>>> firstn(intsfrom(5), 7)\n[5, 6, 7, 8, 9, 10, 11]\n\n>>> def exclude_multiples(n, ints):\n...     for i in ints:\n...         if i % n:\n...             yield i\n\n>>> firstn(exclude_multiples(3, intsfrom(1)), 6)\n[1, 2, 4, 5, 7, 8]\n\n>>> def sieve(ints):\n...     prime = ints.next()\n...     yield prime\n...     not_divisible_by_prime = exclude_multiples(prime, ints)\n...     for p in sieve(not_divisible_by_prime):\n...         yield p\n\n>>> primes = sieve(intsfrom(2))\n>>> firstn(primes, 20)\n[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]\n\n\nAnother famous problem:  generate all integers of the form\n    2**i * 3**j  * 5**k\nin increasing order, where i,j,k >= 0.  Trickier than it may look at first!\nTry writing it without generators, and correctly, and without generating\n3 internal results for each result output.\n\n>>> def times(n, g):\n...     for i in g:\n...         yield n * i\n>>> firstn(times(10, intsfrom(1)), 10)\n[10, 20, 30, 40, 50, 60, 70, 80, 90, 100]\n\n>>> def merge(g, h):\n...     ng = g.next()\n...     nh = h.next()\n...     while 1:\n...         if ng < nh:\n...             yield ng\n...             ng = g.next()\n...         elif ng > nh:\n...             yield nh\n...             nh = h.next()\n...         else:\n...             yield ng\n...             ng = g.next()\n...             nh = h.next()\n\nThe following works, but is doing a whale of a lot of redundant work --\nit\'s not clear how to get the internal uses of m235 to share a single\ngenerator.  Note that me_times2 (etc) each need to see every element in the\nresult sequence.  So this is an example where lazy lists are more natural\n(you can look at the head of a lazy list any number of times).\n\n>>> def m235():\n...     yield 1\n...     me_times2 = times(2, m235())\n...     me_times3 = times(3, m235())\n...     me_times5 = times(5, m235())\n...     for i in merge(merge(me_times2,\n...                          me_times3),\n...                    me_times5):\n...         yield i\n\nDon\'t print "too many" of these -- the implementation above is extremely\ninefficient:  each call of m235() leads to 3 recursive calls, and in\nturn each of those 3 more, and so on, and so on, until we\'ve descended\nenough levels to satisfy the print stmts.  Very odd:  when I printed 5\nlines of results below, this managed to screw up Win98\'s malloc in "the\nusual" way, i.e. the heap grew over 4Mb so Win98 started fragmenting\naddress space, and it *looked* like a very slow leak.\n\n>>> result = m235()\n>>> for i in range(3):\n...     print firstn(result, 15)\n[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24]\n[25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60, 64, 72, 75, 80]\n[81, 90, 96, 100, 108, 120, 125, 128, 135, 144, 150, 160, 162, 180, 192]\n\nHeh.  Here\'s one way to get a shared list, complete with an excruciating\nnamespace renaming trick.  The *pretty* part is that the times() and merge()\nfunctions can be reused as-is, because they only assume their stream\narguments are iterable -- a LazyList is the same as a generator to times().\n\n>>> class LazyList:\n...     def __init__(self, g):\n...         self.sofar = []\n...         self.fetch = g.next\n...\n...     def __getitem__(self, i):\n...         sofar, fetch = self.sofar, self.fetch\n...         while i >= len(sofar):\n...             sofar.append(fetch())\n...         return sofar[i]\n\n>>> def m235():\n...     yield 1\n...     # Gack:  m235 below actually refers to a LazyList.\n...     me_times2 = times(2, m235)\n...     me_times3 = times(3, m235)\n...     me_times5 = times(5, m235)\n...     for i in merge(merge(me_times2,\n...                          me_times3),\n...                    me_times5):\n...         yield i\n\nPrint as many of these as you like -- *this* implementation is memory-\nefficient.\n\n>>> m235 = LazyList(m235())\n>>> for i in range(5):\n...     print [m235[j] for j in range(15*i, 15*(i+1))]\n[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24]\n[25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60, 64, 72, 75, 80]\n[81, 90, 96, 100, 108, 120, 125, 128, 135, 144, 150, 160, 162, 180, 192]\n[200, 216, 225, 240, 243, 250, 256, 270, 288, 300, 320, 324, 360, 375, 384]\n[400, 405, 432, 450, 480, 486, 500, 512, 540, 576, 600, 625, 640, 648, 675]\n\n\nYe olde Fibonacci generator, LazyList style.\n\n>>> def fibgen(a, b):\n...\n...     def sum(g, h):\n...         while 1:\n...             yield g.next() + h.next()\n...\n...     def tail(g):\n...         g.next()    # throw first away\n...         for x in g:\n...             yield x\n...\n...     yield a\n...     yield b\n...     for s in sum(iter(fib),\n...                  tail(iter(fib))):\n...         yield s\n\n>>> fib = LazyList(fibgen(1, 2))\n>>> firstn(iter(fib), 17)\n[1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584]\n'
  8. syntax_tests = '\n\n>>> def f():\n...     return 22\n...     yield 1\nTraceback (most recent call last):\n  ..\nSyntaxError: \'return\' with argument inside generator (<doctest test.test_generators.__test__.syntax[0]>, line 2)\n\n>>> def f():\n...     yield 1\n...     return 22\nTraceback (most recent call last):\n  ..\nSyntaxError: \'return\' with argument inside generator (<doctest test.test_generators.__test__.syntax[1]>, line 3)\n\n"return None" is not the same as "return" in a generator:\n\n>>> def f():\n...     yield 1\n...     return None\nTraceback (most recent call last):\n  ..\nSyntaxError: \'return\' with argument inside generator (<doctest test.test_generators.__test__.syntax[2]>, line 3)\n\nThis one is fine:\n\n>>> def f():\n...     yield 1\n...     return\n\n>>> def f():\n...     try:\n...         yield 1\n...     finally:\n...         pass\nTraceback (most recent call last):\n  ..\nSyntaxError: \'yield\' not allowed in a \'try\' block with a \'finally\' clause (<doctest test.test_generators.__test__.syntax[4]>, line 3)\n\n>>> def f():\n...     try:\n...         try:\n...             1//0\n...         except ZeroDivisionError:\n...             yield 666  # bad because *outer* try has finally\n...         except:\n...             pass\n...     finally:\n...         pass\nTraceback (most recent call last):\n  ...\nSyntaxError: \'yield\' not allowed in a \'try\' block with a \'finally\' clause (<doctest test.test_generators.__test__.syntax[5]>, line 6)\n\nBut this is fine:\n\n>>> def f():\n...     try:\n...         try:\n...             yield 12\n...             1//0\n...         except ZeroDivisionError:\n...             yield 666\n...         except:\n...             try:\n...                 x = 12\n...             finally:\n...                 yield 12\n...     except:\n...         return\n>>> list(f())\n[12, 666]\n\n>>> def f():\n...    yield\nTraceback (most recent call last):\nSyntaxError: invalid syntax\n\n>>> def f():\n...    if 0:\n...        yield\nTraceback (most recent call last):\nSyntaxError: invalid syntax\n\n>>> def f():\n...     if 0:\n...         yield 1\n>>> type(f())\n<type \'generator\'>\n\n>>> def f():\n...    if "":\n...        yield None\n>>> type(f())\n<type \'generator\'>\n\n>>> def f():\n...     return\n...     try:\n...         if x==4:\n...             pass\n...         elif 0:\n...             try:\n...                 1//0\n...             except SyntaxError:\n...                 pass\n...             else:\n...                 if 0:\n...                     while 12:\n...                         x += 1\n...                         yield 2 # don\'t blink\n...                         f(a, b, c, d, e)\n...         else:\n...             pass\n...     except:\n...         x = 1\n...     return\n>>> type(f())\n<type \'generator\'>\n\n>>> def f():\n...     if 0:\n...         def g():\n...             yield 1\n...\n>>> type(f())\n<type \'NoneType\'>\n\n>>> def f():\n...     if 0:\n...         class C:\n...             def __init__(self):\n...                 yield 1\n...             def f(self):\n...                 yield 2\n>>> type(f())\n<type \'NoneType\'>\n\n>>> def f():\n...     if 0:\n...         return\n...     if 0:\n...         yield 2\n>>> type(f())\n<type \'generator\'>\n\n\n>>> def f():\n...     if 0:\n...         lambda x:  x        # shouldn\'t trigger here\n...         return              # or here\n...         def f(i):\n...             return 2*i      # or here\n...         if 0:\n...             return 3        # but *this* sucks (line 8)\n...     if 0:\n...         yield 2             # because it\'s a generator\nTraceback (most recent call last):\nSyntaxError: \'return\' with argument inside generator (<doctest test.test_generators.__test__.syntax[22]>, line 8)\n\nThis one caused a crash (see SF bug 567538):\n\n>>> def f():\n...     for i in range(3):\n...         try:\n...             continue\n...         finally:\n...             yield i\n...\n>>> g = f()\n>>> print g.next()\n0\n>>> print g.next()\n1\n>>> print g.next()\n2\n>>> print g.next()\nTraceback (most recent call last):\nStopIteration\n'
  9.  
  10. def conjoin(gs):
  11.     values = [
  12.         None] * len(gs)
  13.     
  14.     def gen(i, values = values):
  15.         if i >= len(gs):
  16.             yield values
  17.         else:
  18.             for None in gs[i]():
  19.                 values[i] = None
  20.                 for x in gen(i + 1):
  21.                     yield x
  22.                 
  23.             
  24.  
  25.     for x in gen(0):
  26.         yield x
  27.     
  28.  
  29.  
  30. def conjoin(gs):
  31.     n = len(gs)
  32.     values = [
  33.         None] * n
  34.     
  35.     def gen(i, values = values):
  36.         if i >= n:
  37.             yield values
  38.         elif (n - i) % 3:
  39.             ip1 = i + 1
  40.             for None in gs[i]():
  41.                 values[i] = None
  42.                 for x in gen(ip1):
  43.                     yield x
  44.                 
  45.             
  46.         else:
  47.             for x in _gen3(i):
  48.                 yield x
  49.             
  50.  
  51.     
  52.     def _gen3(i, values = values):
  53.         ip1 = i + 1
  54.         ip2 = i + 2
  55.         ip3 = i + 3
  56.         (g, g1, g2) = gs[i:ip3]
  57.         if ip3 >= n:
  58.             for None in g():
  59.                 values[i] = None
  60.                 for None in g1():
  61.                     values[ip1] = None
  62.                     for None in g2():
  63.                         values[ip2] = None
  64.                         yield values
  65.                     
  66.                 
  67.             
  68.         else:
  69.             for None in g():
  70.                 values[i] = None
  71.                 for None in g1():
  72.                     values[ip1] = None
  73.                     for None in g2():
  74.                         values[ip2] = None
  75.                         for x in _gen3(ip3):
  76.                             yield x
  77.                         
  78.                     
  79.                 
  80.             
  81.  
  82.     for x in gen(0):
  83.         yield x
  84.     
  85.  
  86.  
  87. def flat_conjoin(gs):
  88.     n = len(gs)
  89.     values = [
  90.         None] * n
  91.     iters = [
  92.         None] * n
  93.     _StopIteration = StopIteration
  94.     i = 0
  95.     while None:
  96.         
  97.         try:
  98.             while i < n:
  99.                 it = iters[i] = gs[i]().next
  100.                 values[i] = it()
  101.                 i += 1
  102.         except _StopIteration:
  103.             pass
  104.  
  105.         yield values
  106.         i -= 1
  107.         while i >= 0:
  108.             
  109.             try:
  110.                 values[i] = iters[i]()
  111.                 i += 1
  112.             continue
  113.             except _StopIteration:
  114.                 i -= 1
  115.                 continue
  116.             
  117.  
  118.             None<EXCEPTION MATCH>_StopIteration
  119.         break
  120.  
  121.  
  122. class Queens:
  123.     
  124.     def __init__(self, n):
  125.         self.n = n
  126.         rangen = range(n)
  127.         self.rowgenerators = []
  128.         for i in rangen:
  129.             rowuses = [ 0x1L << j | 0x1L << (n + i - j) + n - 1 | 0x1L << (n + 2 * n - 1) + i + j for j in rangen ]
  130.             
  131.             def rowgen(rowuses = rowuses):
  132.                 for j in rangen:
  133.                     uses = rowuses[j]
  134.                     if uses & self.used == 0:
  135.                         self.used |= uses
  136.                         yield j
  137.                         self.used &= ~uses
  138.                         continue
  139.                     self
  140.                 
  141.  
  142.             self.rowgenerators.append(rowgen)
  143.         
  144.  
  145.     
  146.     def solve(self):
  147.         self.used = 0
  148.         for row2col in conjoin(self.rowgenerators):
  149.             yield row2col
  150.         
  151.  
  152.     
  153.     def printsolution(self, row2col):
  154.         n = self.n
  155.         sep = '+' + '-+' * n
  156.         print sep
  157.         for i in range(n):
  158.             squares = [ ' ' for j in range(n) ]
  159.             squares[row2col[i]] = 'Q'
  160.             print '|' + '|'.join(squares) + '|'
  161.             print sep
  162.         
  163.  
  164.  
  165.  
  166. class Knights:
  167.     
  168.     def __init__(self, m, n, hard = 0):
  169.         self.m = m
  170.         self.n = n
  171.         succs = self.succs = []
  172.         
  173.         def remove_from_successors(i0, len = len):
  174.             ne0 = ne1 = 0
  175.             for i in succs[i0]:
  176.                 s = succs[i]
  177.                 s.remove(i0)
  178.                 e = len(s)
  179.                 if e == 0:
  180.                     ne0 += 1
  181.                     continue
  182.                 if e == 1:
  183.                     ne1 += 1
  184.                     continue
  185.             
  186.             if ne0 == 0:
  187.                 pass
  188.             return ne1 < 2
  189.  
  190.         
  191.         def add_to_successors(i0):
  192.             for i in succs[i0]:
  193.                 succs[i].append(i0)
  194.             
  195.  
  196.         
  197.         def first():
  198.             if m < 1 or n < 1:
  199.                 return None
  200.             
  201.             corner = self.coords2index(0, 0)
  202.             remove_from_successors(corner)
  203.             self.lastij = corner
  204.             yield corner
  205.             add_to_successors(corner)
  206.  
  207.         
  208.         def second():
  209.             corner = self.coords2index(0, 0)
  210.             if m < 3 or n < 3:
  211.                 return None
  212.             
  213.             for i, j in ((1, 2), (2, 1)):
  214.                 this = self.coords2index(i, j)
  215.                 final = self.coords2index(3 - i, 3 - j)
  216.                 self.final = final
  217.                 remove_from_successors(this)
  218.                 succs[final].append(corner)
  219.                 self.lastij = this
  220.                 yield this
  221.                 succs[final].remove(corner)
  222.                 add_to_successors(this)
  223.             
  224.  
  225.         
  226.         def advance(len = len):
  227.             candidates = []
  228.             for i in succs[self.lastij]:
  229.                 e = len(succs[i])
  230.                 if e == 1:
  231.                     candidates = [
  232.                         (e, i)]
  233.                     break
  234.                 
  235.                 candidates.append((e, i))
  236.             
  237.             for e, i in candidates:
  238.                 if i != self.final:
  239.                     if remove_from_successors(i):
  240.                         self.lastij = i
  241.                         yield i
  242.                     
  243.                     add_to_successors(i)
  244.                     continue
  245.             
  246.  
  247.         
  248.         def advance_hard(vmid = (m - 1) / 2.0, hmid = (n - 1) / 2.0, len = len):
  249.             candidates = []
  250.             for i in succs[self.lastij]:
  251.                 e = len(succs[i])
  252.                 if e == 1:
  253.                     candidates = [
  254.                         (e, 0, i)]
  255.                     break
  256.                 
  257.                 (i1, j1) = self.index2coords(i)
  258.                 d = (i1 - vmid) ** 2 + (j1 - hmid) ** 2
  259.                 candidates.append((e, -d, i))
  260.             
  261.             for e, d, i in candidates:
  262.                 if i != self.final:
  263.                     if remove_from_successors(i):
  264.                         self.lastij = i
  265.                         yield i
  266.                     
  267.                     add_to_successors(i)
  268.                     continue
  269.             
  270.  
  271.         
  272.         def last():
  273.             yield self.final
  274.  
  275.         self.squaregenerators = None + [
  276.             [
  277.                 first,
  278.                 second] if m * n < 4 else advance] * (m * n - 3) + [
  279.             last]
  280.  
  281.     
  282.     def coords2index(self, i, j):
  283.         return i * self.n + j
  284.  
  285.     
  286.     def index2coords(self, index):
  287.         return divmod(index, self.n)
  288.  
  289.     
  290.     def _init_board(self):
  291.         succs = self.succs
  292.         del succs[:]
  293.         m = self.m
  294.         n = self.n
  295.         c2i = self.coords2index
  296.         offsets = [
  297.             (1, 2),
  298.             (2, 1),
  299.             (2, -1),
  300.             (1, -2),
  301.             (-1, -2),
  302.             (-2, -1),
  303.             (-2, 1),
  304.             (-1, 2)]
  305.         rangen = range(n)
  306.         for i in range(m):
  307.             for j in rangen:
  308.                 s = []
  309.                 succs.append(s)
  310.             
  311.         
  312.  
  313.     
  314.     def solve(self):
  315.         self._init_board()
  316.         for x in conjoin(self.squaregenerators):
  317.             yield x
  318.         
  319.  
  320.     
  321.     def printsolution(self, x):
  322.         m = self.m
  323.         n = self.n
  324.         w = len(str(m * n))
  325.         format = '%' + str(w) + 'd'
  326.         squares = [ [
  327.             None] * n for i in range(m) ]
  328.         k = 1
  329.         for i in x:
  330.             (i1, j1) = self.index2coords(i)
  331.             squares[i1][j1] = format % k
  332.             k += 1
  333.         
  334.         sep = '+' + ('-' * w + '+') * n
  335.         print sep
  336.         for i in range(m):
  337.             row = squares[i]
  338.             print '|' + '|'.join(row) + '|'
  339.             print sep
  340.         
  341.  
  342.  
  343. conjoin_tests = '\n\nGenerate the 3-bit binary numbers in order.  This illustrates dumbest-\npossible use of conjoin, just to generate the full cross-product.\n\n>>> for c in conjoin([lambda: iter((0, 1))] * 3):\n...     print c\n[0, 0, 0]\n[0, 0, 1]\n[0, 1, 0]\n[0, 1, 1]\n[1, 0, 0]\n[1, 0, 1]\n[1, 1, 0]\n[1, 1, 1]\n\nFor efficiency in typical backtracking apps, conjoin() yields the same list\nobject each time.  So if you want to save away a full account of its\ngenerated sequence, you need to copy its results.\n\n>>> def gencopy(iterator):\n...     for x in iterator:\n...         yield x[:]\n\n>>> for n in range(10):\n...     all = list(gencopy(conjoin([lambda: iter((0, 1))] * n)))\n...     print n, len(all), all[0] == [0] * n, all[-1] == [1] * n\n0 1 True True\n1 2 True True\n2 4 True True\n3 8 True True\n4 16 True True\n5 32 True True\n6 64 True True\n7 128 True True\n8 256 True True\n9 512 True True\n\nAnd run an 8-queens solver.\n\n>>> q = Queens(8)\n>>> LIMIT = 2\n>>> count = 0\n>>> for row2col in q.solve():\n...     count += 1\n...     if count <= LIMIT:\n...         print "Solution", count\n...         q.printsolution(row2col)\nSolution 1\n+-+-+-+-+-+-+-+-+\n|Q| | | | | | | |\n+-+-+-+-+-+-+-+-+\n| | | | |Q| | | |\n+-+-+-+-+-+-+-+-+\n| | | | | | | |Q|\n+-+-+-+-+-+-+-+-+\n| | | | | |Q| | |\n+-+-+-+-+-+-+-+-+\n| | |Q| | | | | |\n+-+-+-+-+-+-+-+-+\n| | | | | | |Q| |\n+-+-+-+-+-+-+-+-+\n| |Q| | | | | | |\n+-+-+-+-+-+-+-+-+\n| | | |Q| | | | |\n+-+-+-+-+-+-+-+-+\nSolution 2\n+-+-+-+-+-+-+-+-+\n|Q| | | | | | | |\n+-+-+-+-+-+-+-+-+\n| | | | | |Q| | |\n+-+-+-+-+-+-+-+-+\n| | | | | | | |Q|\n+-+-+-+-+-+-+-+-+\n| | |Q| | | | | |\n+-+-+-+-+-+-+-+-+\n| | | | | | |Q| |\n+-+-+-+-+-+-+-+-+\n| | | |Q| | | | |\n+-+-+-+-+-+-+-+-+\n| |Q| | | | | | |\n+-+-+-+-+-+-+-+-+\n| | | | |Q| | | |\n+-+-+-+-+-+-+-+-+\n\n>>> print count, "solutions in all."\n92 solutions in all.\n\nAnd run a Knight\'s Tour on a 10x10 board.  Note that there are about\n20,000 solutions even on a 6x6 board, so don\'t dare run this to exhaustion.\n\n>>> k = Knights(10, 10)\n>>> LIMIT = 2\n>>> count = 0\n>>> for x in k.solve():\n...     count += 1\n...     if count <= LIMIT:\n...         print "Solution", count\n...         k.printsolution(x)\n...     else:\n...         break\nSolution 1\n+---+---+---+---+---+---+---+---+---+---+\n|  1| 58| 27| 34|  3| 40| 29| 10|  5|  8|\n+---+---+---+---+---+---+---+---+---+---+\n| 26| 35|  2| 57| 28| 33|  4|  7| 30| 11|\n+---+---+---+---+---+---+---+---+---+---+\n| 59|100| 73| 36| 41| 56| 39| 32|  9|  6|\n+---+---+---+---+---+---+---+---+---+---+\n| 74| 25| 60| 55| 72| 37| 42| 49| 12| 31|\n+---+---+---+---+---+---+---+---+---+---+\n| 61| 86| 99| 76| 63| 52| 47| 38| 43| 50|\n+---+---+---+---+---+---+---+---+---+---+\n| 24| 75| 62| 85| 54| 71| 64| 51| 48| 13|\n+---+---+---+---+---+---+---+---+---+---+\n| 87| 98| 91| 80| 77| 84| 53| 46| 65| 44|\n+---+---+---+---+---+---+---+---+---+---+\n| 90| 23| 88| 95| 70| 79| 68| 83| 14| 17|\n+---+---+---+---+---+---+---+---+---+---+\n| 97| 92| 21| 78| 81| 94| 19| 16| 45| 66|\n+---+---+---+---+---+---+---+---+---+---+\n| 22| 89| 96| 93| 20| 69| 82| 67| 18| 15|\n+---+---+---+---+---+---+---+---+---+---+\nSolution 2\n+---+---+---+---+---+---+---+---+---+---+\n|  1| 58| 27| 34|  3| 40| 29| 10|  5|  8|\n+---+---+---+---+---+---+---+---+---+---+\n| 26| 35|  2| 57| 28| 33|  4|  7| 30| 11|\n+---+---+---+---+---+---+---+---+---+---+\n| 59|100| 73| 36| 41| 56| 39| 32|  9|  6|\n+---+---+---+---+---+---+---+---+---+---+\n| 74| 25| 60| 55| 72| 37| 42| 49| 12| 31|\n+---+---+---+---+---+---+---+---+---+---+\n| 61| 86| 99| 76| 63| 52| 47| 38| 43| 50|\n+---+---+---+---+---+---+---+---+---+---+\n| 24| 75| 62| 85| 54| 71| 64| 51| 48| 13|\n+---+---+---+---+---+---+---+---+---+---+\n| 87| 98| 89| 80| 77| 84| 53| 46| 65| 44|\n+---+---+---+---+---+---+---+---+---+---+\n| 90| 23| 92| 95| 70| 79| 68| 83| 14| 17|\n+---+---+---+---+---+---+---+---+---+---+\n| 97| 88| 21| 78| 81| 94| 19| 16| 45| 66|\n+---+---+---+---+---+---+---+---+---+---+\n| 22| 91| 96| 93| 20| 69| 82| 67| 18| 15|\n+---+---+---+---+---+---+---+---+---+---+\n'
  344. weakref_tests = "Generators are weakly referencable:\n\n>>> import weakref\n>>> def gen():\n...     yield 'foo!'\n...\n>>> wr = weakref.ref(gen)\n>>> wr() is gen\nTrue\n>>> p = weakref.proxy(gen)\n\nGenerator-iterators are weakly referencable as well:\n\n>>> gi = gen()\n>>> wr = weakref.ref(gi)\n>>> wr() is gi\nTrue\n>>> p = weakref.proxy(gi)\n>>> list(p)\n['foo!']\n\n"
  345. __test__ = {
  346.     'tut': tutorial_tests,
  347.     'pep': pep_tests,
  348.     'email': email_tests,
  349.     'fun': fun_tests,
  350.     'syntax': syntax_tests,
  351.     'conjoin': conjoin_tests,
  352.     'weakref': weakref_tests }
  353.  
  354. def test_main(verbose = None):
  355.     test_support = test_support
  356.     test_generators = test_generators
  357.     import test
  358.     test_support.run_doctest(test_generators, verbose)
  359.  
  360. if __name__ == '__main__':
  361.     test_main(1)
  362.  
  363.